class Solution {
public:
    bool check(vector<int>&position,int m,int x){
        int pre=position[0];
        int cnt=1;
        int n=position.size();
        for(int i=1;i<n;++i){
            if(position[i]-pre >= x){
                pre=position[i];
                cnt++;
            }
        }
        return cnt >= m;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(),position.end());
        int l=1;
        int r=position.back()-position[0];
        while(l<r){
            int mid=l+(r-l+1)/2;
            if(check(position,m,mid)){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
};
